package top.hkyzf.study.leetcode.graph;

import org.junit.Test;

/**
 * description: 
 * @author zhufeng
 * @date 2024/3/16 0016 19:08
 * @version V1.0
 */
public class 矩阵中移动的最大次数_2684 {
    private int rtn = 0;
    public int maxMoves(int[][] grid) {
        int[] dir = {-1, 0 , 1};
        int[] pos = {0, 0};
        for (int i = 0; i < grid.length; i++) {
            pos[0] = i;
            dfs(grid, pos, dir, grid.length, grid[0].length);
        }
        return rtn;
    }

    private void dfs(int[][] grid, int[] pos, int[] dirs, int row, int col) {
        // 已经遍历过最后一列
        if (rtn == col-1) {
            return;
        }
        for (int dir : dirs) {
            int[] curPos = {pos[0] + dir, pos[1] + 1};
            // 越界检查
            if (curPos[0] < 0 || curPos[1] >= col) {
                rtn = Math.max(pos[1], rtn);
                continue;
            }
            if (curPos[0] >= row) {
                rtn = Math.max(pos[1], rtn);
                break;
            }
            // 未越界，判断是否访问过
            if (grid[curPos[0]][curPos[1]] == 0) {
                continue;
            }
            // 继续递归
            if (grid[curPos[0]][curPos[1]] > grid[pos[0]][pos[1]]) {
                rtn = Math.max(curPos[1], rtn);
                dfs(grid, curPos, dirs, row, col);
                grid[curPos[0]][curPos[1]] = 0;
            } else {
                rtn = Math.max(pos[1], rtn);
            }
        }
    }

    @Test
    public void testMaxMoves () {
        int[][] grid = {
                {153,178,258,12,26,80,175,34,147,296,262,185,144,129},
                {232,148,9,83,238,144,100,35,204,193,269,231,279,155},
                {172,260,213,132,237,47,170,172,27,101,102,1,156,249},
                {141,124,185,133,69,195,89,5,133,11,296,149,28,107},
                {62,252,289,287,45,48,36,177,159,2,294,291,68,19},
                {123,246,67,254,281,176,171,53,21,141,53,19,264,138},
                {16,22,227,12,86,171,292,240,296,1,56,222,269,57},
                {46,295,194,204,56,29,139,146,272,300,300,163,278,269},
                {60,240,175,186,109,193,27,276,104,17,164,216,254,7},
                {274,253,259,116,257,14,85,145,59,276,126,248,254,183},
                {258,40,214,256,163,193,162,135,242,35,177,67,90,127},
                {165,227,115,81,83,267,284,43,273,104,236,171,260,47},
                {62,276,180,42,149,246,288,227,126,290,140,276,188,167},
                {204,171,47,124,219,214,20,131,100,110,123,203,95,242},
                {16,182,195,290,162,124,181,299,115,170,290,216,173,261}};
        System.out.println(maxMoves(grid));
    }
}
